/**
 * 两种操作，强制在线
 * 1. u v： 连接u和v，保证任意时刻都是森林
 * 2. u v： 问是u和v是否存在共同的邻居，显然最多有一个
 * 很明显link-cut-tree
 * 对于操作2，首先将u做成根，然后access(v)，于是u和v在同一条链上
 * 如果u、v有共同的邻居，必然满足以下条件：
 * 1. 链上有且只有三个节点
 * 2. 将v旋成树根，只有两种情况：
 *      1. 某个节点是v的左儿子，u是该节点的左儿子，则该节点为答案
 *      2. u是v的左儿子，且u有右儿子，则答案是u的右儿子
 * 
 * 标程提供了一个根号做法，没看懂如何分块
 * 另外有一种启发式合并的方法，维护树，对1操作，将小树向大树合并。
 * 总合并时间是O(NlogN)的。
 */
#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std;


struct lct_t{ // link-cut-tree, 1-index, 只能处理路径

using data_type = int;  // 数据类型
using value_type = int; // 维护的信息类型
using lazy_type = int;  // 延迟标记类型

enum {LEFT = 0, RIGHT = 1};

struct node_t{
    int parent;
	int son[2];
	data_type data;   // 点权
	value_type value; // 信息
    int size;         // 伸展树上的size，也是信息之一
	lazy_type lazy;   // 延迟标记
	int flip;      // 翻转标记
};

int N;
vector<node_t> Nodes;
int toUsed;

static value_type mkValue(const data_type & data){
	// assert(0);
    return 0;
}

// 从下往上计算value，用于pushUp,伸展树应保证ls与rs均有意义
value_type _up_(const value_type & ls, const value_type & rs) {
	// assert(0);
    return 0;
}

// 根据变动信息delta计算本节点的信息并且打延迟标记，用于pushDown或者modify
// flip其实也是延迟标记的一部分，这里只计算t，跟t的儿子无关
// 要维护t的data、value和lazy、flip
void _dn_(int t, const lazy_type & delta, int flip) {
	// assert(0);
    if(flip){
        swap(Nodes[t].son[LEFT], Nodes[t].son[RIGHT]);
        Nodes[t].flip ^= 1;
    }
}

/// init之后要手工初始化节点并且link
void init(int n){
	// Nodes.assign((N = n) + 1, {0, {0, 0}, data_zero(), value_zero(), 0, lazy_zero(), 0});
    Nodes.clear();
    Nodes.reserve((N = n) + 1);
    toUsed = 0;
	return;
}

int _newNode(const data_type & data){
    memset(Nodes.data()+(++toUsed),0,sizeof(node_t));
    Nodes[toUsed].data = data;
    _pushUp(toUsed);
    return toUsed;
}

// 根据t节点的儿子，计算t节点
void _pushUp(int t) {
	auto & n = Nodes[t];
	n.value = mkValue(n.data);
    n.size = 1;
    int son = n.son[LEFT];
	if(son) {
		n.size += Nodes[son].size;
		n.value = _up_(Nodes[son].value, n.value);
	}
	son = n.son[RIGHT];
	if(son) {
		n.size += Nodes[son].size;
		/// 必须t在左、右儿子在右
		n.value = _up_(n.value, Nodes[son].value);
	}
	return;
}

// 根据t的延迟去计算t的儿子
void _pushDown(int t) {
	auto & n = Nodes[t];
    if(n.lazy == lazy_zero() and n.flip == 0) return;
	
	int son;
	auto & lz = n.lazy;
	auto flip = n.flip;
	if(son = Nodes[t].son[LEFT]) _dn_(son, lz, flip);
	if(son = Nodes[t].son[RIGHT]) _dn_(son, lz, flip);

	lz = lazy_zero();
	n.flip = 0;
	return;
}

/// 判断t是否为本splay的根
/// 父亲为零（真树根?），父亲的左右儿子不是t
bool _isRoot(int t){
    int p = Nodes[t].parent;
    return 0 == p or (Nodes[p].son[LEFT] != t and Nodes[p].son[RIGHT] != t);
}

//获取排行，不能用于树根
int _getSN(int t){
    return Nodes[Nodes[t].parent].son[RIGHT] == t ? RIGHT : LEFT;
}

inline void _link(int p,int sn,int t){
    Nodes[Nodes[t].parent = p].son[sn] = t;
}

inline void _rotate(int t){
    int p = Nodes[t].parent;//父节点
    int g = Nodes[p].parent;//祖父节点
    int sn = _getSN(t);
    int osn = sn ^ 1;
    //不需要pushDown，在splay中pushDown

    _link(p, sn, Nodes[t].son[osn]);
    Nodes[t].parent = g;
    if(not _isRoot(p)) Nodes[g].son[_getSN(p)] = t;
    _link(t,osn,p);

    _pushUp(p);
	return;
}

//从根开始逐级下放延迟标记
void _maintain(int t){
    if(not _isRoot(t)) _maintain(Nodes[t].parent);
    _pushDown(t);
}

void _splay(int t){
    _maintain(t);
    while(!_isRoot(t)){
        int p = Nodes[t].parent;
        if(!_isRoot(p)) _getSN(t)==_getSN(p)?_rotate(p):_rotate(t);
        _rotate(t);
    }
    _pushUp(t);
}

//从根到x形成一条链，返回
int _access(int x){
    int t = 0;
    for(;x;x=Nodes[t=x].parent){
        _splay(x);
        Nodes[x].son[RIGHT] = t;//将链接上
        _pushUp(x);
    }
    return t;
}

//令x成为原树的根
void _makeRoot(int x){
    _access(x);
    _splay(x);
    _dn_(x, lazy_zero(), 1);
	return;
}

//获取x所在树的根节点
int _getRoot(int x){
    _access(x);
    _splay(x);
    while( Nodes[x].son[LEFT] ) x = Nodes[x].son[LEFT];
    _splay(x);
    return x;
}
//令child是parent的子节点
void link(int parent,int child){
    _makeRoot(child);
    Nodes[child].parent = parent; // 注意这里不能用 _link
}

//将child从parent树上切下
void cut(int parent,int child){
    _makeRoot(parent);
    _access(child);
    _splay(child);
    Nodes[child].son[LEFT] = Nodes[Nodes[child].son[LEFT]].parent = 0;
    _pushUp(child);
}
//在root做树根的情况下，x和y的最近公共祖先
int lca(int root,int x,int y){
    _makeRoot(root);
    _access(x);
    return _access(y);
}
bool isConnect(int x,int y){
    return x == y || _getRoot(x) == _getRoot(y);
}

static const data_type & data_zero(){
    static const data_type DATA_0 = 0;
	return DATA_0;
}

static const value_type & value_zero(){
    static const value_type VALUE_0 = 0;
	return VALUE_0;
}

static const lazy_type & lazy_zero(){
    static const lazy_type LAZY_0 = 0;
	return LAZY_0;
}

};

using llt = long long;
llt const MOD = 998244353;

lct_t Tree;
int N, Q;

void work(){
    cin >> N >> Q;
    Tree.init(N);
    for(int i=1;i<=N;++i)Tree._pushUp(Tree._newNode(i));

    llt x = 0;
    for(int q=1;q<=Q;++q){
        llt a, b, c; 
        cin >> a >> b >> c;
        a = 1 + a * (x + 1) % MOD % 2;
        b = 1 + b * (x + 1) % MOD % N;
        c = 1 + c * (x + 1) % MOD % N;
#ifndef ONLINE_JUDGE
        cout << q << ": " << a << " " << b << " " << c << endl;
#endif
        if(1 == a){
            Tree.link(b, c);
        }else{
            x = 0;
            if(Tree.isConnect(b, c)){
                Tree._makeRoot(b);
                Tree._access(c);
                Tree._splay(c);
                if(Tree.Nodes[c].size == 3){
                    int son = Tree.Nodes[c].son[lct_t::LEFT];
                    if(son){
                        if(son != b){
                            int tmp = Tree.Nodes[son].son[lct_t::LEFT];
                            if(tmp == b) x = Tree.Nodes[son].data;                        
                        }else{
                            int tmp = Tree.Nodes[son].son[lct_t::RIGHT];
                            if(tmp) x = Tree.Nodes[tmp].data;  
                        }
                    }                    
                }                
            }
            cout << x << "\n";
        }
    }
    return;
}

int main(){
#ifndef ONLINE_JUDGE
    freopen("z.txt", "r", stdin);
#endif
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int nofkase = 1;
    // cin >> nofkase;
    while(nofkase--) work();
    return 0;
}